//a b c d e   f g
//a b e c d h f g
// c d e   2 3 4
//e c d h  4 2 3 0    这个索引指的是在老的中的索引 0代表之前不存在

// [c,d]
// [0,1] //通过上面两个序列 可以求出来 最终这样的结果  就可以保证某些元素不用移动

// 需要求 连续性最强的子序列
//  贪心算法 + 二分查找

// 潜力值
// eg1
//2 3 7 6 8 4 9 11  ->求最长子序列的个数
//2
//2 3
//2 3 7
//2 3 6 (2 3 6 的潜力更强 因为6后可以跟7)
//2 3 6 8
//2 3 4 8 (记录 4将6 换掉) (8 要记录他前面原本是6)
//2 3 4 8 9
//2 3 4 8 9 11

//eg2: 2 3 1 5 6 8 7 9 4
//2 (2的前一个是null)
//2 3 (3的前一个是2)
//1 3 (1的前一个是null)
//1 3 5 (5的前一个是3)
//1 3 5 6 (6的前一个是5)
//1 3 5 6 8 (8的前一个是6)
//1 3 5 6 7 (7的前一个是6)
//1 3 5 6 7 9 (9的前一个是7)
//1 3 4 6 7 9 (4的前一个是3)

//然后根据记录的倒着写求 如：最后一个是9 9前是7 7前是6 6前是5 5前是3 3前是2
//9 7 6 5 3 2
//则最长递增子序列是 2 3 5 6 7 9
// 找更有潜力的  但是由于中间有替换的情况 但是没关系 因为他的后一个记录了前一个是谁

// 4 2 3 0
// 4
// 2 (2前是null)
// 2 3 (3前是2)
// 0 3 (0前是null)

//3 2
//2 3

//实现最长递增子序列
function getSequence(arr) {
  const result = [0]; //初始化一个数组用来存索引
  const p = result.slice(0); //用来记录前面一个数据所对应的索引值 进行倒序追溯
  let start;
  let end;
  let middle;
  const len = arr.length; //终止条件
  for (let i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) {
      //为了vue3 而处理掉数组中0的情况 [5 3 4 0]
      //拿出result的最后一个元素和我们当前的这一项做比对
      let resultLastIndex = result[result.length - 1];
      if (arr[resultLastIndex] < arrI) {
        result.push(i); //将当前索引放入到结果集即可
        p[i] = resultLastIndex; //正常放入的时候前一个数据的索引是result的最后一个元素
        console.log(result);

        continue;
      }
    }
    //如果arr中的当前项小于最后一个元素 通过二分查找 找到min[比当前项大的那个]
    start = 0;
    end = arr.length - 1;
    while (start < end) {
      middle = ((start + end) / 2) | 0;
      if (arr[result[middle]] < arrI) {
        start = middle + 1;
      } else {
        end = middle;
      }
    }
    //进行值的替换
    if (arrI < arr[result[start]]) {
      //将p[i]的值替换成要被替换的值的前一个的索引
      p[i] = result[start - 1];
      result[start] = i;
      console.log(result);
    }
  }
  //p为前驱节点的列表 需要根据最后一个节点做追溯
  let l = result.length;
  let last = result[l - 1]; //取出最后一项

  while (l-- > 0) {
    result[l] = last;
    last = p[last]; //在数组中找到最后一个
  }

  //需要创建一个前驱节点用来记录前面一个数据所对应的索引值 进行倒序追溯 因为最后一项肯定是正确的

  return result;
}

[1, 2, 3, 4, 5, 8, 9];

console.log(getSequence([2, 3, 1, 5, 6, 8, 7, 9, 4]));
